This invention relates to a single modular component which can be used to:
(1)Add modulo (2.sup.n -1) PA1 (2) Subtract modulo (2.sup.n -1) PA1 (3) Code a 2n-bit integer into its least positive residue modulo (2.sup.n -1) PA1 (4) Combine the residue of an integer modulo 2.sup.n and an integer modulo (2.sup.n -1) to obtain the n most significant bits of the integer modulo 2.sup.n (2.sup.n -1). The n-least significant bits are the same as the integer modulo (2.sup.n) input. The invention when used in conjunction with residue multipliers, correlators, convolvers, transversal filters, microprocessors, one for modulos 2.sup.n and one for modulo (2.sup.n -1), allows a simple double-precision module to be constructed.
The mathematical basis for combining the results for different moduli which are pairwise relatively prime has been known for nearly a thousand years, and is called the Chinese Remainder Theorem. The Chinese Remainder Theorem is a simple formula for the remainder obtained by dividing a number by a composite number (i.e. a number m=m.sub.1 m.sub.2 with M.sub.1 and m.sub.2 both greater than one) in terms of the remainders obtained by dividing the number by each of the factors of the composite number m (i.e. m.sub.1 and m.sub.2).
Additional information on this theorem, as well as general information on residue class arithmetic, may be obtained from U.S. Pat. No. 4,041,284 by James W. Bond, entitled SIGNAL PROCESSING DEVICES USING RESIDUE CLASS ARITHMETIC, which issued on 19 Aug. 1977. However, simple digital implementations of the Chinese Remainder Theorem in terms of shifts and adds of the input data have not been known. Instead the standard approach has been to combine the inputs to obtain an intermediate representation of the answer in a form known as the mixedradix representation. This is described by Szabo, N.S. & Tanaka, R.I., Residue Arithmetic and Its Applications to Computer Arithemtic, McGraw Hill 1967.
The limitation of this prior art approach is the complexity of the logic required and the limited speed the logic can be used to combine inputs. The inventions described are simpler and faster than previously known approaches to implementing the Chinese Remainder Theorem for the use of the moduli 2.sup.n and (2.sup.n -1).
Addition and subtraction modulo 2.sup.n is simple. Addition is accomplished by using ordinary binary n-bit adders and ignoring the carry bit. Subtraction is performed using ordinary binary adders along with inverters. To calculate a-b the following is done:
(a) Inverters are used to form (2.sup.n -1) -b, the bit by bit complement of the binary number b.
(b) An ordinary binary adder with carry input is used to calculate a +((2.sup.n -1)+1. If the carry-out is ignored, the output is congruent to a-b modulo 2.sup.n. Thus all modulo 2.sup.n additions and subtractions can be accomplished using readily available digital components. The inventions described provide a simple means for accomplishing the coding, combining (or decoding), necessary for doing double precision calculations via the moduli 2.sup.n and 2.sup.n -1.